package linkedlist;

import java.util.StringJoiner;

public class ReverseLinkedList2 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        out(head);
        ListNode head2 = reverse(head, 2, 4);
        out(head2);
    }

    private static ListNode reverse(ListNode head, int m, int n) {
        if (head == null || m >= n) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        head = dummy;

        for (int i = 1; i < m; i++) {
            head = head.next;
        }

        ListNode prevM = head;
        ListNode nodeM = head.next;
        ListNode nodeN = nodeM;
        ListNode postN = nodeN.next;
        for (int i = m; i < n; i++) {
            ListNode next = postN.next;
            postN.next = nodeN;
            nodeN = postN;
            postN = next;
        }

        prevM.next = nodeN;
        nodeM.next = postN;
        return dummy.next;
    }


    static class ListNode {

        Object val;

        ListNode next;

        public ListNode(Object value) {
            this.val = value;
        }

    }


    public static void out(ListNode head) {
        StringJoiner stringJoiner = new StringJoiner(" -> ");
        ListNode head2 = head;
        while (head2 != null) {
            stringJoiner.add(head2.val + "");
            head2 = head2.next;
        }
        System.out.println(stringJoiner);
    }

}


